In various applications, search on large amount of information is needed to acquire information meeting special conditions. Generally, an index is built in advance for original information. After that, search is performed in the index to find out a matching item in response to a search request, and thereby related information is retrieved. Due to various reasons, a searcher always wish to get a complete set of resulted information of search, that is, all information satisfying the search condition. However, the existing techniques for indexing and searching do not guarantee completeness of search.
With wide use of computer network and communication technique, data owner often stores data files on a server(s) maintained by a third party. In such application, the service of searching on data files stored on a server is also provided by a third party. That is to say, the third party who provided the search service looks up data files stored on the server by using the index in response to a request from a searcher, and provides the search result to the searcher. Since the substantive work in searching is performed by the third party, it is even more desired in such situation that the correctness and completeness of search can be verified and ensured.
In addition, with the concern of privacy and safety, data files are often stored after being encrypted. Especially in the above case of storage service, files are often stored in a ciphertext form on the server to prevent the contents of the files from revealing to unauthorized users (in some case, also including the third party who provides the storage and search services). However, the encrypted storage of the files makes it difficult to search on files, and especially makes it hard to verify correctness and completeness of the search result.